import java.util.Arrays;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列 重新排列成 字典序中下一个更大的排列。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须原地修改，只允许使用额外常数空间。
 * <p>
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 */
class Solution {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 6, 5, 4, 3, 2, 1,};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 题干的意思是：找出这个数组排序出的所有数中，刚好比当前数大的那个数
     * <p>
     * 比如当前 nums = [1,2,3]。这个数是123，找出1，2，3这3个数字排序可能的所有数，排序后，比123大的那个数 也就是132
     * <p>
     * 如果当前 nums = [3,2,1]。这就是1，2，3所有排序中最大的那个数，那么就返回1，2，3排序后所有数中最小的那个，也就是1，2，3 -> [1,2,3]
     *
     * @param nums
     */
    public static void nextPermutation(int[] nums) {
        if (nums.length > 1) {
            // 最后两个数字比较，如果倒数第二个比倒数第一大，是的话就开始处理, 否则重复判断，直到比到第一个
            boolean unMatch = true;
            for (int i = nums.length - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    // 如果匹配到了，则开始处理
                    // 找到nums[i + 1]后面刚刚好大于nums[i]的数字，如果没有的话就只是互换
                    int j = i + 1;
                    for (; j < nums.length; j++) {
                        if (nums[j] <= nums[i]) {
                            break;
                        }
                    }
                    j -= 1;
                    // 现在的j是刚刚好比i大，互换位置，然后倒序
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    for (int left = i + 1, right = nums.length - 1; left < right; left++, right--) {
                        tmp = nums[left];
                        nums[left] = nums[right];
                        nums[right] = tmp;
                    }
                    unMatch = false;
                    break;
                }
            }
            if (unMatch) {
                // 如果最后没比出来，则改为升序排列
                int tmp;
                for (int left = 0, right = nums.length - 1; left < right; left++, right--) {
                    tmp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = tmp;
                }
            }

        }
    }
}